Let đˇ\mathbf{\Pi} be a properly scaled JL matrix (random , sparse random etc.) with m=O(dĪĩ2)m=O(\frac{d}{\epsilon^2}) rows1. Then with probability 9/109/10, for any đâânÃd\mathbf{A} \in \mathbb{R}^{n \times d} and đâân\mathbf{b} \in \mathbb{R}^n, âĨđđąĖâđâĨ22â¤(1+Īĩ)âĨđđą*âđâĨ22\lVert \mathbf{A}\tilde{\mathbf{x}}-\mathbf{b}\rVert_2^2 \leq (1+\epsilon)\lVert \mathbf{A}\mathbf{x}^*-\mathbf{b}\rVert_2^2 where đąĖ=argminđąâĨđˇđđąâđˇđâĨ22\tilde{\mathbf{x}} = \arg\min_\mathbf{x}\lVert \mathbf{\Pi Ax}-\mathbf{\Pi b}\rVert_2^2.
this can be improved to O(d/Īĩ)O(d/\epsilon) with tighter analysisâŠī¸